//************************************************************
//    > File Name: merge_sort.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月14日  9:56:43
//***********************************************************

#include<bits/stdc++.h>
using namespace std;
void merge_core(vector<int>& a,int begin,int mid,int end){
	int i,j,k=end-begin;
	vector<int> tmp(k,0);
	for(i=mid,j=end;i!=begin&&j!=mid;)
		tmp[--k]= (a[i-1]>a[j-1]?a[--i]:a[--j]);
	for(;i!=begin;tmp[--k]=a[--i]);
	for(;j!=mid;tmp[--k]=a[--j]);
	for(i=begin,k=0;i<end;a[i++]=tmp[k++]);
		
}
void merge_sort(vector<int>& a,int begin,int end){
	if(end-begin<2) return;
	int mid=(end-begin)>>1;
	merge_sort(a,begin,mid);
	merge_sort(a,mid,end);
	merge_core(a,begin,mid,end);
}

int main(){
	vector<int> a;
	a.push_back(6);
	a.push_back(4);
	cout<<a.at(0)<<" "<<a.at(1)<<endl;
	merge_sort(a,0,a.size());
	cout<<a.at(0)<<" "<<a.at(1)<<endl;
}
